package math;

import javafx.util.Pair;

import java.util.HashSet;
import java.util.Set;
import java.util.Stack;

/**
 * @author pengfei.hpf
 * @date 2020/3/21
 * @verdion 1.0.0
 */
public class CanMeasureWater {

    //超出时间限制
//    public boolean canMeasureWater(int x, int y, int z) {
//        if(x + y < z){
//            return false;
//        }
//        Stack<int[]> stack = new Stack<>();
//        stack.push(new int[]{0,0});
//        Set<String> visited = new HashSet<>();
//        while(!stack.isEmpty()){
//            int[] remain = stack.pop();
//            int remainX = remain[0];
//            int remainY = remain[1];
//            String key = remainX + "#" + remainY;
//            if(visited.contains(key)){
//                continue;
//            }
//            visited.add(key);
//            if(remainX == z || remainY == z || remainX + remainY == z){
//                return true;
//            }
//            stack.push(new int[]{x, remainY});
//            stack.push(new int[]{y, remainX});
//            stack.push(new int[]{remainX, 0});
//            stack.push(new int[]{remainY, 0});
//            int minX = Math.min(remainX, y - remainY);
//            stack.push(new int[]{remainX - minX, remainY + minX});
//            int minY = Math.min(remainY, x - remainX);
//            stack.push(new int[]{remainX + minY, remainY - minY});
//        }
//        return false;
//
//    }

    public boolean canMeasureWater(int x, int y, int z) {
        if(x + y < z){
            return false;
        }
        if( x == 0 || y == 0){
            return z == 0 || x + y == z;
        }

        return z % GCD(x, y) == 0;

    }

     //TODO: GCD
    private int GCD(int a,int b) {
        if(b==0)
            return a;
        else
            return GCD(b,a%b);
    }


    public boolean canMeasureWaterII(int x, int y, int z) {
        if(x + y < z){
            return false;
        }
        Stack<Pair<Integer, Integer>> stack = new Stack<>();
        stack.push(new Pair<>(0,0));
        Set<Pair<Integer, Integer>> visited = new HashSet<>();
        while(!stack.isEmpty()){
            Pair<Integer, Integer> remain = stack.pop();
            int remainX = remain.getKey();
            int remainY = remain.getValue();
            if(visited.contains(remain)){
                continue;
            }
            visited.add(remain);
            if(remainX == z || remainY == z || remainX + remainY == z){
                return true;
            }
            stack.push(new Pair<>(x, remainY));
            stack.push(new Pair<>(remainX, y));
            stack.push(new Pair<>(remainX, 0));
            stack.push(new Pair<>(0, remainY));
            int minX = Math.min(remainX, y - remainY);
            stack.push(new Pair<>(remainX - minX, remainY + minX));
            int minY = Math.min(remainY, x - remainX);
            stack.push(new Pair<>(remainX + minY, remainY - minY));
        }
        return false;

    }
    

}
